package com.leetcode.p200;

import com.utils.DataUtils;

public class Test200 {

    private int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private int count = 0;

    public int numIslands(char[][] grid) {

        boolean[][] visited = new boolean[grid.length][grid[0].length];

        for (int m = 0; m < grid.length; m++) {
            for (int n = 0; n < grid[0].length; n++) {
                if (!visited[m][n] && grid[m][n] == '1') {
                    count++;
                    help(grid, m, n, visited);
                }
            }
        }

        return count;
    }

    public void help(char[][] grid, int m, int n, boolean[][] visited) {
        if (grid[m][n] == '0' || visited[m][n]) {
            return;
        }

        visited[m][n] = true;

        for (int i = 0; i < direction.length; i++) {
            int nextM = m + direction[i][0];
            int nextN = n + direction[i][1];

            if (nextM >= 0 && nextM < grid.length && nextN >= 0 && nextN < grid[0].length) {
                help(grid, nextM, nextN, visited);
            }
        }
    }

    public static void main(String[] args) {
        Test200 test = new Test200();

        char[][] grid = {{'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}};

//        char[][] grid = {{'1', '1'},
//                {'1', '0'},
//        };

//        char[][] grid = {{'1', '1', '0', '0', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '1', '0', '0'},
//                {'0', '0', '0', '1', '1'}
//        };


        DataUtils.printDoubleArrayByChar(grid);

        System.out.println(test.numIslands(grid));
    }
}
